#pragma once
#include<iostream>
using namespace std;
template<class T>
class BST_Node
{
public:
	BST_Node(T _val=0)
		:val(_val),
		left(nullptr),
		right(nullptr)
	{
		
	}
	T val;
	BST_Node* left;
	BST_Node* right;
};

template<class k>
class BST
{
public:
	typedef BST_Node<k> Node;

	BST()
		:root(nullptr)
	{ }

	bool insert(const k& val)
	{
		Node* newNode = new Node(val);
		Node* parent = nullptr;
		Node* _root = root;
		if (root == nullptr)
		{
			root = newNode;
		}
		else
		{
			while (_root)
			{
				parent = _root;
				if (val < _root->val)
				{
					_root = _root->left;
				}
				else
				{
					if (val == _root->val)
					{
						delete newNode;
						return false;
					}
					_root = _root->right;
				}
			}
			if (val < parent->val)
			{
				parent->left = newNode;
			}
			else
			{
				parent->right = newNode;
			}
		}
		return true;
	}

	Node* find(const k& key)
	{
		Node* _root = root;
		while (_root)
		{
			if (key < _root->val)
			{
				_root = _root->left;
			}
			else
			{
				if (key == _root->val)
				{
					return _root;
				}
				else
				{
					_root = _root->right;
				}
			}
		}
		return _root;
	}

	bool erase(const k& key)
	{
		Node* it = find(key);
		if ( it == nullptr)
		{
			return false;
		}
		Node* parent = nullptr,*_root = root;
		while (_root->val != key)
		{
			parent = _root;
			if (key < _root->val)
			{
				_root = _root->left;
			}
			else
			{
				_root = _root->right;
			}
		}
		if (it->left == nullptr && it->right == nullptr)
		{
			if (parent == nullptr)
			{
				root = nullptr;
			}
			else
			{
				if (parent->left == it)
				{
					parent->left = nullptr;
				}
				else
				{
					parent->right = nullptr;
				}
			}
			delete it;
		}
		else
		{
			if (it->left == nullptr || it->right == nullptr)
			{
				Node* child = (it->left != nullptr) ? it->left : it->right;
				if (parent == nullptr)
				{
					root = child;
				}
				else
				{
					if (parent->left == it)
					{
						parent->left = child;
					}
					else
					{
						parent->right = child;
					}
				}
				delete it;
			}
			else
			{		
				Node* temp = it->right,*pa=it;
				while (temp->left)
				{
					pa = temp;
					temp = temp->left;
				}
				k tp = it->val;
				it->val = temp->val;
				temp->val = tp;
				if (pa->left == temp)
				{
					pa->left = temp->right;
				}
				else
				{
					pa->right = temp->right;
				}

				delete temp;
			}
		}
		return true;
	}

	void show()
	{
		_show(root);
		cout << endl;
	}
	void _show(Node* _root)
	{
		if (_root == nullptr)
		{
			return;
		}
		_show(_root->left);
		cout << _root->val<<" ";
		_show(_root->right);
	}


private:
	Node* root;
};

